package com.echo.boot.structure.tree.binarytree;

import java.util.Comparator;

/**
 * Created with IntelliJ IDEA
 * Created By CQ
 * Date: 2020/5/11
 * Time: 15:20
 *
 * @author Administrator
 */
public class BinarySearchTree<E> extends BinaryTree<E> {
    private Comparator<E> comparator;

    public BinarySearchTree() {
        this(null);
    }

    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    public void add(E element) {
        elementNotNullCheck(element);
        // 添加第一个元素
        if (root == null) {
            root = createNode(element, null);
            size++;
            afterAdd(root);
            return;
        }

        Node<E> parent = root;
        Node<E> node = root;
        int cmp = 0;
        while (node != null) {
            parent = node;
            cmp = compareTo(element, node.element);
            if (cmp < 0) {
                node = node.left;
            } else if (cmp > 0) {
                node = node.right;
            } else {
                // 相等的覆盖.
                node.element = element;
                return;
            }
        }
        Node<E> newNode = createNode(element, parent);
        if (cmp < 0) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }
        size++;
        afterAdd(newNode);
    }

    protected void afterAdd(Node<E> node) {

    }

    protected void afterRemove(Node<E> node) {

    }


    public void remove(E element) {
        if (element == null) {
            return;
        }
        remove(node(element));
    }

    /**
     * @author CQ
     * @DESCRIPTION: 删除节点
     * @params: [node]
     * @return: void
     * @Date: 2020/5/20 10:06
     * @Modified By:
     */
    private void remove(Node<E> node) {
        if (node == null) {
            return;
        }
        size--;
        // 度为2的节点
        if (node.hasTwoChildren()) {
            // 找到后继节点
//            Node<E> s = predecessor(node);
            Node<E> s = successor(node);
            // 用后继节点的值覆盖度为2的节点的值
            node.element = s.element;
            // 删除后继节点
            node = s;
        }
        // 删除node节点( node节点必然是 1 或者 0)
        // 删除node节点（node的度必然是1或者0）
        Node<E> replacement = node.left != null ? node.left : node.right;
        // node是度为1的节点
        if (replacement != null) {
            // 更改parent
            replacement.parent = node.parent;
            // 更改parent的left、right的指向
            if (node.parent == null) {
                // node是度为1的节点并且是根节点
                root = replacement;
            } else if (node == node.parent.left) {
                node.parent.left = replacement;
            } else {
                // node == node.parent.right
                node.parent.right = replacement;
            }
            // 删除节点后的调整
            afterRemove(replacement);
        } else if (node.parent == null) {
            // node是叶子节点并且是根节点
            root = null;
            // 删除节点后的调整
            afterRemove(node);
        } else {
            // node是叶子节点，但不是根节点
            if (node == node.parent.left) {
                node.parent.left = null;
            } else {
                node.parent.right = null;
            }
            // 删除节点后的调整
            afterRemove(node);
        }
    }

    /**
     * @author CQ
     * @DESCRIPTION: 元素查找节点
     * @params: [element]
     * @return: Node<E>
     * @Date: 2020/5/20 10:04
     * @Modified By:
     */
    private Node<E> node(E element) {
        Node<E> node = root;
        while (node != null) {
            int cmp = compareTo(element, node.element);
            if (cmp == 0) {
                return node;
            }
            if (cmp > 0) {
                node = node.right;
            }
            if (cmp < 0) {
                node = node.left;
            }
        }
        return null;
    }


    public boolean contains(E element) {
        return node(element) != null;
    }

    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }


    /**
     * @author CQ
     * @DESCRIPTION: 比较两个值
     * @params: e1 父节点,e2 比较的值
     * @return: 返回值等于0, 代表e1和e2相等;返回值大于0.代表e1大于e2;返回值小于0,,代表e1小于e2;
     * @Date: 2020/5/13 8:47
     * @Modified By:
     */
    private int compareTo(E e1, E e2) {
        if (comparator != null) {
            return comparator.compare(e1, e2);
        }
        return ((Comparable<E>) e1).compareTo(e2);
    }


    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        toString(root, sb, "");
        return sb.toString();
    }

    public void toString(Node<E> node, StringBuilder sb, String prefix) {
        if (node == null) {
            return;
        }
        sb.append(prefix).append(node.element).append("\r\n");
        toString(node.left, sb, prefix + "---");
        toString(node.right, sb, prefix + "---");
    }


}
